package basic;

/**
 * Created on 2019/10/11.
 */
public class SortingTest {

    public static void main(String[] args) {
        int[] a = {4, 5, 6, 1, 3, 2};
//        insertionSort(a, a.length);
//        easySort(a);
//        sortFast(a, 0, a.length-1);
//        int[] a = {11, 8, 3, 9, 7, 1, 2, 5};
//        Merge.sort(a);
//        countingSort(a, a.length);
//        Arrays.sort(a);
        heapSort(a,a.length-1);
        for (int i : a) {
            System.out.print(i + "->");
        }
        System.out.println("");

        //二分查找
//        System.out.println(sqrt(2.0, 6));

        /*  查找第一个等于给定值的元素 0
            最后一个等于值 1
            第一个大于等于值 2
            最后一个小于等于值 3 */
        a = new int[]{1, 3, 4, 5, 6, 8, 8, 8, 11, 18};
        for (int i : a) {
            System.out.print(i + "->");
        }
        System.out.println("");
//        System.out.println(biSearch(a, 8, 0));
//        System.out.println(biSearch(a, 8, 1));
//        System.out.println(biSearch2(a, 7, 2));
//        System.out.println(biSearch3(a, 9, 3));
        //打印排列组合
//        a = new int[]{1, 2, 3, 4};
//        printPermutations(a, 4, 4);

    }

    public static void easySort(int[] a) {//选择排序
        for (int i = 0; i < a.length; i++) {
            int k = i;
            for (int j = i+1; j < a.length; j++) {
                if (a[k] > a[j]) {
                    k = j;
                }
            }
            //互换
            int temp = a[i];
            a[i] = a[k];
            a[k] = temp;
        }
    }

    // 插入排序，a 表示数组，n 表示数组大小
    public static void insertionSort(int[] a, int n) {
        if (n <= 1) return;
        for (int i = 1; i < n; ++i) {
            int value = a[i];
            int j = i - 1;
            // 查找插入的位置
            for (; j >= 0; --j) {
                if (a[j] > value) {
                    a[j+1] = a[j];  // 数据移动
                } else {
                    break;
                }
            }
            a[j+1] = value; // 插入数据
        }
    }

    //递归快速排序
    public static void sortFast(int[] a, int low, int high) {
        //已经排完
        if (low >= high) {
            return;
        }
        int left = low;
        int right = high;

        //保存基准值
        int pivot = a[left];
        while (left < right) {
            //从后向前找到比基准小的元素
            while (left < right && a[right] >= pivot)
                right--;
            a[left] = a[right];
            //从前往后找到比基准大的元素
            while (left < right && a[left] <= pivot)
                left++;
            a[right] = a[left];
        }
        // 放置基准值，准备分治递归快排
        a[left] = pivot;
        sortFast(a, low, left - 1);
        sortFast(a, left + 1, high);
    }

    public static void sortThreeWay(int[] a, int lo, int hi) {
        if (lo >= hi) {
            return;
        }
        int v = a[lo], lt = lo, i = lo + 1, gt = hi;
        while (i <= gt) {
            if (a[i] < v) {
                swap(a, i++, lt++);
            } else if (a[i] > v) {
                swap(a, i, gt--);
            } else {
                i++;
            }
        }
        sortThreeWay(a, lo, lt - 1);
        sortThreeWay(a, gt + 1, hi);
    }

    private static void swap(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
    public static class Merge {

        //归并所需的辅助数组
        private static int[] aux;

        public static void sort(int[] a) {
            //一次性分配空间
            aux = new int[a.length];
            sort(a, 0, a.length - 1);
        }

        private static void sort(int[] a, int low, int high) {
            if (low >= high) {
                return;
            }
            int mid = (low + high) / 2;
            //将左半边排序
            sort(a, low, mid);
            //将右半边排序
            sort(a, mid + 1, high);
            merge(a, low, mid, high);
        }

        /**
         * 该方法先将所有元素复制到aux[]中，然后在归并会a[]中。方法咋归并时(第二个for循环)
         * 进行了4个条件判断：
         * - 左半边用尽(取右半边的元素)
         * - 右半边用尽(取左半边的元素)
         * - 右半边的当前元素小于左半边的当前元素(取右半边的元素)
         * - 右半边的当前元素大于等于左半边的当前元素(取左半边的元素)
         * @param a
         * @param low
         * @param mid
         * @param high
         */
        private static void merge(int[] a, int low, int mid, int high) {
            //将a[low..mid]和a[mid+1..high]归并
            int i = low, j = mid + 1;
            for (int k = low; k <= high; k++) {
                aux[k] = a[k];
            }

            for (int k = low; k <= high; k++) {
                if (i > mid) {
                    a[k] = aux[j++];
                } else if (j > high) {
                    a[k] = aux[i++];
                } else if (aux[j] < aux[i]) {
                    a[k] = aux[j++];
                } else {
                    a[k] = aux[i++];
                }
            }
        }
    }

    // 计数排序，a 是数组，n 是数组大小。假设数组中存储的都是非负整数。
    public static void countingSort(int[] a, int n) {
        if (n <= 1) return;
        // 查找数组中数据的范围
        int max = a[0];
        for (int i = 1; i < n; ++i) {
            if (max < a[i]) {
                max = a[i];
            }
        }
        int[] c = new int[max + 1]; // 申请一个计数数组 c，下标大小 [0,max]
        for (int i = 0; i <= max; ++i) {
            c[i] = 0;
        }
        // 计算每个元素的个数，放入 c 中
        for (int i = 0; i < n; ++i) {
            c[a[i]]++;
        }
        // 依次累加
        for (int i = 1; i <= max; ++i) {
            c[i] = c[i-1] + c[i];
        }
        // 临时数组 r，存储排序之后的结果
        int[] r = new int[n];
        // 计算排序的关键步骤，有点难理解
        for (int i = n - 1; i >= 0; --i) {
            int index = c[a[i]]-1;
            r[index] = a[i];
            c[a[i]]--;
        }
        // 将结果拷贝给 a 数组
        for (int i = 0; i < n; ++i) {
            a[i] = r[i];
        }
    }

    public static double sqrt(double x, double precision) {
        if (x < 0) {
            return Double.NaN;
        }
        double low = 0;
        double up = x;
        if (x < 1 && x > 0) {
            /** 小于1的时候*/
            low = x;
            up = 1;
        }
        double mid = low + (up - low)/2;
        while(( mid+"").length() - (mid+"").indexOf(".") -1 <precision ) {
//        while(up - low > precision) {
            if (mid * mid > x ) {//TODO mid可能会溢出
                up = mid;
            } else if (mid * mid < x) {
                low = mid;
            } else {
                return mid;
            }
            mid = low + (up - low)/2;
        }
        return mid;
    }

    public static int biSearch(int[] a, int val, int type) {
        int low = 0;
        int hi = a.length - 1;
        while (low <= hi) {
            int mid = low + (hi - low) / 2;
            if (a[mid] > val) {
                hi = mid - 1;
            }else if (a[mid] < val) {
                low = mid + 1;
            }else {
                if (type == 0) {  //查找第一个等于给定值的元素 0
                    if (mid == 0 || a[mid-1] != val) return mid;
                    hi = mid - 1;
                } else if (type == 1) { //最后一个等于值 1
                    if (mid == a.length-1 || a[mid+1] != val) return mid;
                    low = mid + 1;
                }
            }
        }
        return -1;
    }

    public static int biSearch2(int[] a, int val, int type) {
        int low = 0;
        int hi = a.length - 1;
        while (low <= hi) {
            int mid = low + (hi - low) / 2;
            if (a[mid] < val) {
                low = mid + 1;
            }else {
                if (type == 2) { //第一个大于等于值 2
                    if (mid == 0 || a[mid-1] < val) return mid ;
                    hi = mid - 1;
                }
            }
        }
        return -1;
    }

    public static int biSearch3(int[] a, int val, int type) {
        int low = 0;
        int hi = a.length - 1;
        while (low <= hi) {
            int mid = low + (hi - low) / 2;
            if (a[mid] > val) {
                hi = mid - 1;
            }else {
                 if (type == 3) { //最后一个小于等于值 3
                    if (mid == a.length-1 || a[mid+1] > val) return mid;
                    low = mid + 1;
                }
            }
        }
        return -1;
    }


    private static void buildHeap(int[] a, int n) {
        for (int i = n/2; i >= 1; --i) {
            heapify(a, n, i);
        }
    }

    private static void heapify(int[] a, int n, int i) {
        while (true) {
            int maxPos = i;
            if (i*2 <= n && a[i] < a[i*2]) maxPos = i*2;
            if (i*2+1 <= n && a[maxPos] < a[i*2+1]) maxPos = i*2+1;
            if (maxPos == i) break;
            swap(a, i, maxPos);
            i = maxPos;
        }
    }


    // n表示数据的个数，数组a中的数据从下标1到n的位置。
    public static void heapSort(int[] a, int n) {
        buildHeap(a, n);
        int k = n;
        while (k > 1) {
            swap(a, 1, k);
            --k;
            heapify(a, k, 1);
        }
    }

    // 调用方式：
// int[]a = a={1, 2, 3, 4}; printPermutations(a, 4, 4);
// k表示要处理的子数组的数据个数
    public static void printPermutations(int[] data, int n, int k) {
        if (k == 1) {
            for (int i = 0; i < n; ++i) {
                System.out.print(data[i] + " ");
            }
            System.out.println();
        }

        for (int i = 0; i < k; ++i) {
            int tmp = data[i];
            data[i] = data[k-1];
            data[k-1] = tmp;

            printPermutations(data, n, k - 1);

            tmp = data[i];
            data[i] = data[k-1];
            data[k-1] = tmp;
        }
    }

}
